import java.util.ArrayList;
import java.util.List;

public class LogicList<T> {

    class LocInfo{
        int outer;
        int inner;
        public LocInfo(int outer, int inner) {
            this.outer = outer;
            this.inner = inner;
        }
    }

    private List<List<T>> lists;
    private List<Long> prefixSum;
    private int threshold;
    private int size;

    void initLogicList(int threshold){
        this.threshold = threshold;
        this.lists = new ArrayList<>();
        this.prefixSum = new ArrayList<>();
        prefixSum.add(0L);
        lists.add(new ArrayList<>(threshold));
    }

    LogicList(){
        initLogicList(1000);
    }

    LogicList(int threshold){
        initLogicList(threshold);
    }

    private void maintainPrefix(int startInd, long fixNum){
        for (int i = startInd; i < prefixSum.size(); i++) {
            prefixSum.set(i, prefixSum.get(i) + fixNum);
        }
    }

    private LocInfo getLoc(long loc) throws IndexOutOfBoundsException{
        if(loc >= size){
            throw new IndexOutOfBoundsException();
        }
        int left = 0, right = prefixSum.size() - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            long midNum = prefixSum.get(mid);
            if(midNum == loc){
                return new LocInfo(mid+1, 0);
            }
            else if(midNum < loc){
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return new LocInfo(left, (int) (loc - (left == 0? 0:prefixSum.get(left - 1))));
    }

    private void appendListWithEle(int loc, T ele){
        List<T> tmpLastList = new ArrayList<>(threshold);
        tmpLastList.add(ele);
        lists.add(loc, tmpLastList);
        long lastNum = loc == 0 ? 0:prefixSum.get(loc - 1);
        prefixSum.add(loc, lastNum);
    }

    public int getSize() {
        return size;
    }

    public T get(long loc) throws IndexOutOfBoundsException{
        LocInfo locInfo = getLoc(loc);
        return lists.get(locInfo.outer).get(locInfo.inner);
    }

    public void add(T ele){
        List<T> lastList = lists.get(lists.size() - 1);
        if(lastList.size() < threshold){
            lastList.add(ele);
        }
        else{
            appendListWithEle(lists.size(), ele);
        }
        size++;
        maintainPrefix(lists.size() - 1, 1L);
    }

    public void add(long loc, T ele) throws IndexOutOfBoundsException{
        LocInfo locInfo = getLoc(loc);
        int outerLoc = locInfo.outer;
        List<T> tmpList = lists.get(outerLoc);
        if(tmpList.size() >= threshold) {
            T lastEle = tmpList.remove(tmpList.size() - 1);
            int nextOuterLoc = outerLoc+1;
            if(nextOuterLoc >= lists.size() || lists.get(nextOuterLoc).size() >= threshold){
                appendListWithEle(nextOuterLoc, lastEle);
            }
            else{
                lists.get(nextOuterLoc).add(0, lastEle);
            }
            maintainPrefix(nextOuterLoc, 1L);
        }
        else{
            maintainPrefix(outerLoc, 1L);
        }
        tmpList.add(locInfo.inner, ele);
        size++;
    }

    public T remove(long loc) throws IndexOutOfBoundsException{
        LocInfo locInfo = getLoc(loc);
        int outerLoc = locInfo.outer;
        List<T> tmpList = lists.get(outerLoc);
        T delEle = tmpList.remove(locInfo.inner);
        size--;
        maintainPrefix(outerLoc, -1L);
        if(tmpList.isEmpty()){
            lists.remove(outerLoc);
            prefixSum.remove(outerLoc);
        }
        return delEle;
    }

    public static void main(String[] args) {
        LogicList logicList = new LogicList(1000);
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            logicList.add(i);
        }
        System.out.println(System.currentTimeMillis() - startTime);

        startTime = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            logicList.add(i, i);
        }
        System.out.println(System.currentTimeMillis() - startTime);

        startTime = System.currentTimeMillis();
        for (int i = 0; i < 1010000; i++) {
            logicList.get(i);
        }
        System.out.println(System.currentTimeMillis() - startTime);

        startTime = System.currentTimeMillis();
        for (int i = 0; i < 1010000; i++) {
            logicList.remove(0);
        }
        System.out.println(System.currentTimeMillis() - startTime);
    }
}
